UVa/11503 - Virtual Friends/11503.cc

   1 #include <iostream>
   2 #include <map>
   3 using namespace std;
   4
   5 /* Union find */
   6 const int NN = 100005;
   7 int p[NN], rank[NN];
   8 void make_set(int x){ p[x] = x, rank[x] = 0; }
   9 void link(int x, int y){ rank[x] > rank[y] ? p[y] = x : p[x] = y, rank[x] == rank[y] ? rank[y]++: 0; }
  10 int find_set(int x){ return x != p[x] ? p[x] = find_set(p[x]) : p[x]; }
  11 void merge(int x, int y){ link(find_set(x), find_set(y)); }
  12 /* End union find */
  13
  14 int f[NN];
  15
  16 int main(){
  17   int t;
  18   cin >> t;
  19   while (t--){
  20     for (int i=0; i<NN; ++i) make_set(i), f[i] = 1;
  21
  22     int curID = 0;
  23     map<string, int> id;
  24     int e;
  25     cin >> e;
  26     while (e--){
  27       string s, t;
  28       cin >> s >> t;
  29       int a, b;
  30       if (id.count(s)) a = id[s];
  31       else a = id[s] = curID++;
  32       if (id.count(t)) b = id[t];
  33       else b = id[t] = curID++;
  34
  35       int i, j;
  36       if ((i = find_set(a)) == (j = find_set(b))){
  37         cout << f[i] << endl;
  38       }else{
  39         int all = f[i] + f[j];
  40         merge(a, b);
  41         f[find_set(a)] = all;
  42         cout << all << endl;
  43       }
  44     }
  45   }
  46   return 0;
  47 }